#include<iostream>
using namespace std;
#include<vector>
#include<stack>
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), ans = 0;
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            int pos = i - 2 * dp[i - 1] - 2;
            if (pos < 0)
                continue;
            if (s[i - 1] == ')' && s[pos] == '(') {
                dp[i] = dp[i - 1] + 1;
                if (pos - 1 >= 0)
                    dp[i] += dp[pos];
            }
            ans = max(ans, 2 * dp[i]);
        }
        return ans;
    }
};